package offer;

public class offerII_0097 {
    public int numDistinct(String s, String t) {
        char[] s1=s.toCharArray();
        char[] t1=t.toCharArray();
        int lens=s.length();
        int lent=t.length();
        int[][] dp=new int[lens][lent];
        if(s1[0]==t1[0]) dp[0][0]=1;
        for(int i=1;i<lens;++i){
            dp[i][0]=dp[i-1][0];
            if(s1[i]==t1[0]) dp[i][0]+=1;
        }
        for(int i=1;i<lens;++i){
            for(int j=1;j<lent;++j){
                if(s1[i]==t1[j]){
                    dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];
                }
                else dp[i][j]+=dp[i-1][j];
            }
        }
        return dp[lens-1][lent-1];
    }

}
